package oj_leetcode;

public class PartitionList {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode rPre = dummy;
        while(head != null){
            ListNode end = rPre;
            while(head != null && head.val < x){
                end = head;
                head = head.next;
            }
            if(rPre == end){
                rPre = head;
                head = head.next;
            }else if(pre == rPre){
                rPre = head;
                pre = end;
            }else{
                ListNode tmp = end.next;
                end.next = pre.next;
                pre.next = rPre.next;
                rPre.next = tmp;
                pre = end;
            }
        }
        return dummy.next;
    }
}
